package person.bing.fbcloud.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: mengfanbing
 * @date: 2020/8/6 8:58
 */
public class Q336 {
    public static void main(String[] args) {
        String[] param = {"abcd","dcba","lls","s","sssll"};
        List<List<Integer>> lists = palindromePairs(param);
        System.out.println(lists);
    }

    //超时
    public static List<List<Integer>> palindromePairs(String[] words) {
        //两两配对，拼接成两个新的字符串
        //判断新字符串是否回文
        List<List<Integer>> ans = new ArrayList<>();
        if (words == null){
            return ans;
        }
        int length = words.length;
        if (length < 2){
            return ans;
        }
        for(int i=0;i<length-1;i++){
            for(int j=i+1;j<length;j++){
                String left = words[i];
                String right = words[j];
                String concat1 = left.concat(right);
                String concat2 = right.concat(left);
                //判断回文
                Boolean palindrome1 = isPalindrome(concat1);
                if (palindrome1){
                    List<Integer> list = new ArrayList<>();
                    list.add(i);
                    list.add(j);
                    ans.add(list);
                }
                Boolean palindrome2 = isPalindrome(concat2);
                if (palindrome2){
                    List<Integer> list = new ArrayList<>();
                    list.add(j);
                    list.add(i);
                    ans.add(list);
                }
            }
        }
        return ans;
    }

    public static Boolean isPalindrome(String str){
        int length = str.length();
        int left = 0;
        int right = length-1;
        while (left<right){
            if (str.substring(left,left+1).equals(str.substring(right,right+1))){
                left++;
                right--;
            }else {
                return false;
            }
        }
        return true;
    }
}
